package com.cn.algorithm.two.divide;


public class Divide {

    public static void main(String[] args) {
        int[] arr = new int[]{-2, 1, -3, 4, -1, 2, 1, -5, 4};
        System.out.println(maxSubArray3(arr));

        System.out.println(lengthOfLIS(new int[] {10, 2, 2, 5, 1, 7, 101, 18}));
        //int len = lcs2(new int[] {1, 3, 5, 9, 10}, new int[] {1, 4, 9, 10});
        //System.out.println(len);

        //System.out.println(lcsOfLength("ADBBBA", "ABBA"));

    }

    /*
     *
     * 求最大连续子序列之和
     * 解法一：暴力法
     */
    public static int maxSubArray1(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int max = Integer.MIN_VALUE;
        for (int i = 0; i < arr.length - 1; i++) {
            int k = arr[i];
            for (int j = 1 + i; j < arr.length; j++) {
                k += arr[j];
                max = Math.max(k, max);
            }
        }
        return max;
    }

    /*
     * 求最大连续子序列之和
     * 解法二 分治
     */
    public static int maxSubArray2(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        return maxSubArray2(arr, 0, arr.length);
    }

    private static int maxSubArray2(int[] arr, int start, int end) {
        if (end - start <= 1) {
            return arr[start];
        }
        int mid = (start + end) >> 1;
        int leftMax = arr[mid - 1];
        int leftSum = leftMax;
        for (int i = mid - 2; i >= start; i--) {
            leftSum += arr[i];
            leftMax = Math.max(leftMax, leftSum);
        }
        int rightMax = arr[mid];
        int rightSum = rightMax;
        for (int i = mid + 1; i < end; i++) {
            rightSum += arr[i];
            rightMax = Math.max(rightMax, rightSum);
        }
        return Math.max(leftMax + rightMax,
                Math.max(maxSubArray2(arr, start, mid), maxSubArray2(arr, mid, end)));
    }


    /*
     * 求最大连续子序列之和
     * 解法三 分治
     */
    private static int maxSubArray3(int[] arr) {
        if (arr == null || arr.length == 0) {
            return -1;
        }
        int max = arr[0];
        int dp = max;
        for (int i = 1; i < arr.length; i++) {
            if (dp > 0) {
                dp = dp + arr[i];
            } else {
                dp = arr[i];
            }
            max = Math.max(dp, max);
        }
        return max;
    }


    /*
    *  最长上升子序列
    */
    private static int lengthOfLIS(int[] arr) {
        if (arr == null || arr.length == 0) {
            return 0;
        }
        int[] dp = new int[arr.length];
        int max = dp[0] = 1;
        for (int i = 1; i < dp.length; i++) {
            dp[i] = 1;
            for (int j = 0; j < i; j++) {
                if (arr[j] >= arr[i]) {
                    continue;
                }
                dp[i] = Math.max(dp[i], dp[j] + 1);
            }
            max = Math.max(max, dp[i]);
        }
        return max;
    }

    /*
    * 最长公共子序列
    * 解法一
    */
    public static int lcs(int[] num1, int[] num2) {
        if (num1 == null || num1.length == 0) {
            return 0;
        }
        if ( num2 == null || num2.length == 0) {
            return 0;
        }
        return lcs(num1, num1.length, num2, num2.length);
    }

    private static int lcs(int[] num1, int i, int[] num2, int j) {
        if (i == 0 || j == 0) {
            return 0;
        }
        if (num1[i - 1] != num2[j - 1]) {
            return Math.max(lcs(num1, i - 1, num2, j), lcs(num1, i, num2, j - 1));
        }
        return lcs(num1, i - 1, num2, j - 1) + 1;
    }


    /*
     * 最长公共子序列
     * 解法二
     */
    public static int lcs2(int[] num1, int[] num2) {
        if (num1 == null || num1.length == 0) {
            return 0;
        }
        if ( num2 == null || num2.length == 0) {
            return 0;
        }
        int[][] dp = new int[num1.length + 1][num2.length + 1];
        for (int i = 1; i <= num1.length; i++) {
            for (int j = 1; j <= num2.length; j++) {
                if (num1[i - 1] == num2[j - 1]) {
                    dp[i][j] = dp[i - 1][j - 1] + 1;
                } else {
                    dp[i][j] = Math.max(dp[i][j - 1], dp[i - 1][j]);
                }
            }
        }
        return dp[num1.length][num2.length];
    }

    /*
    * 最长公共子串(连续的子序列)
    */
    public static int lcsOfLength(String a, String b) {
        if ( a == null || b == null) {
            return 0;
        }
        int max = 0;
        return max;
    }

}
